﻿// 4004. 传送阵.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
/*
https://www.acwing.com/problem/content/4007/

给定一个 n×n
 的方格矩阵，行、列编号为 1∼n
，其中第 i
 行第 j
 列的方格坐标为 (i,j)
。

每个方格要么是平地，要么是陷阱。

旅行者从方格 (r1,c1)
 出发，要前往方格 (r2,c2)
 处。

出发点和目的地保证都是平地。

旅行者每次移动可以沿上、下、左、右四个方向，移动一格距离。

移动过程中，不得走出矩阵或进入陷阱。

由于存在陷阱的原因，旅行者可能无法顺利抵达目的地。

幸运的是，他可以任意选择两个平地方格，在上面建立一对传送阵。

传送阵能够支持旅行者在两个平地方格之间自由传送。

但是，建立传送阵是一笔不容小视的花费。

在方格 (rs,cs)
 和 (rt,ct)
 处建立传送阵，所需成本为 (rs−rt)2+(cs−ct)2
。

请你计算，为了使旅行者能够成功抵达目的地，建立传送阵所需花费的最低成本。

如果旅行者可以无需建立传送阵，直接走到目的地，那么成本就是 0
。

注意，最多只能建立一对传送阵。

输入格式
第一行包含整数 n
，表示矩阵尺寸。

第二行包含两个整数 r1,c1
，表示起点方格坐标为 (r1,c1)
。

第三行包含两个整数 r2,c2
，表示目的地方格坐标为 (r2,c2)
。

接下来 n
 行，每行包含一个长度为 n
 的 01
 字符串，其中第 i
 行第 j
 个字符如果为 0
，则表示方格 (i,j)
 是平地，如果为 1
，则表示方格 (i,j)
 是陷阱。

输出格式
输出一个整数，表示为了确保旅行能够成功，所需花费的最小成本。

数据范围
前三个测试点满足，1≤n≤10
。
所有测试点满足，1≤n≤50
，1≤r1,c1,r2,c2≤n
。

输入样例1：
5
1 1
5 5
00001
11111
00111
00110
00110
输出样例1：
10
输入样例2：
3
1 3
3 1
010
101
010
输出样例2：
8
输入样例3：
1
1 1
1 1
0
输出样例3：
0
*/
#include <iostream>

int main()
{
    std::cout << "Hello World!\n";
}

 